/*
leetcode 202：快乐数
编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

 

示例 1：

输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
示例 2：

输入：n = 2
输出：false
 

提示：

1 <= n <= 2^31 - 1
*/
#include <iostream>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> seen; // 用于存储已经出现过的数字，检测循环
        
        //如果 find(n) 返回 seen.end()，表示 n 不存在于集合中，查找失败。
        //如果 find(n) 返回的迭代器不是 seen.end()，表示 n 存在于集合中，查找成功。
        while (n != 1 && seen.find(n) == seen.end()) {
            seen.insert(n);     // 将当前数字加入集合
            n = getNext(n);     // 计算下一步的平方和
        }
        return n == 1;          // 如果 n == 1，返回 true；否则进入循环，返回 false
    }

private:
    int getNext(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10; // 提取个位数,如果 n = 123，则 digit = 123 % 10 = 3
            sum += digit * digit; // 累加平方
            n /= 10;             // 去掉个位,如果 n = 123，执行 n /= 10 后，n = 12
        }
        return sum;
    }
};

int main() {
    Solution solution;
    int n = 2;
    if (solution.isHappy(n)) {
        cout << n << " is a happy number!" << endl;
    } else {
        cout << n << " is not a happy number!" << endl;
    }
    return 0;
}
/*
算法步骤和推演
初始值：
输入数字：n = 2
seen 集合：空集合 {}

第一步：计算平方和
当前数字：n = 2
计算平方和：
2^2=4
更新数字：n = 4
检查 4 是否在 seen 集合中：否，将 4 加入集合。
集合更新为：{2}

第二步：计算平方和
当前数字：n = 4
计算平方和：
4^2=16
更新数字：n = 16
检查 16 是否在 seen 集合中：否，将 16 加入集合。
集合更新为：{2, 4}

第三步：计算平方和
当前数字：n = 16
计算平方和：
1^2+6^2=37
更新数字：n = 37
检查 37 是否在 seen 集合中：否，将 37 加入集合。
集合更新为：{2, 4, 16}

第四步：计算平方和
当前数字：n = 37
计算平方和：
3^2+7^2=58
更新数字：n = 58
检查 58 是否在 seen 集合中：否，将 58 加入集合。
集合更新为：{2, 4, 16, 37}

第五步：计算平方和
当前数字：n = 58
计算平方和：
5^2+8^2=89
更新数字：n = 89
检查 89 是否在 seen 集合中：否，将 89 加入集合。
集合更新为：{2, 4, 16, 37, 58}

第六步：计算平方和
当前数字：n = 89
计算平方和：
8^2+9^2=145
更新数字：n = 145
检查 145 是否在 seen 集合中：否，将 145 加入集合。
集合更新为：{2, 4, 16, 37, 58, 89}

第七步：计算平方和
当前数字：n = 145
计算平方和：
1^2+4^2+5^2=42
更新数字：n = 42
检查 42 是否在 seen 集合中：否，将 42 加入集合。
集合更新为：{2, 4, 16, 37, 58, 89, 145}

第八步：计算平方和
当前数字：n = 42
计算平方和：
4^2+2^2=20
更新数字：n = 20
检查 20 是否在 seen 集合中：否，将 20 加入集合。
集合更新为：{2, 4, 16, 37, 58, 89, 145, 42}

第九步：计算平方和
当前数字：n = 20
计算平方和：
2^2+0^2=4
更新数字：n = 4
检查 4 是否在 seen 集合中：是，说明进入循环。

结论
输入 2 会进入循环，无法到达 1，因此 2 不是一个快乐数。

循环检测
通过集合 seen，我们检测到了循环路径：
2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 (循环)
这是算法检测非快乐数的重要机制，避免了死循环。
*/
